package com.example.system.class09;

/**
 * @Date 2022/7/28
 * @Author Jonathan
 */
public class Code01_TrieTree {

    public static void main(String[] args) {
        TrieTree trieTree = new TrieTree();
        trieTree.insert("dkjh");
        trieTree.insert("dkac");
        System.out.println("search 'dkjh':" + trieTree.search("dkjh"));
        System.out.println("search 'dkac':" + trieTree.search("dkac"));
        System.out.println(trieTree.search("dkac"));
        System.out.println(trieTree.search("dk"));
        System.out.println("prefixNumber:" + trieTree.prefixNumber("dk"));
        trieTree.delete("dkjh");
        System.out.println("====== after delete word 'dkjh' ======");
        System.out.println("prefixNumber:" + trieTree.prefixNumber("dk"));
    }


    // insert(String word)
    // delete(String word)
    // search(String word) word 单词出现过几次
    // int prefixNumber(String pre) 所有加入的字符串中 有几个是以pre这个字符串作为前缀的

    static class TrieTree {

        class Node {
            int pass;
            int end;
            Node[] next;

            public Node() {
                pass = 0;
                end = 0;
                next = new Node[26];
            }
        }

        Node root;

        // 构造函数初始化头结点
        public TrieTree() {
            root = new Node();
        }

        public void insert(String word) {
            if (word == null || word.length() <= 0) {
                return;
            }
            final char[] chars = word.toCharArray();
            Node cur = root;
            for (int i = 0; i < chars.length; i++) {
                char aChar = chars[i];
                int path = aChar - 'a';
                Node node = null;
                // 查找或者创建节点
                if (cur.next[path] == null) {
                    node = new Node();
                } else {
                    node = cur.next[path];
                }
                // 将节点挂上来
                cur.next[path] = node;
                cur.pass++; // 当前节点pass加1
                if (i == chars.length - 1) {
                    // 最后一个节点计数加1
                    node.end++;
                }
                // 将新建的节点作为当前节点
                cur = node;
            }
        }

        public int search(String word) {
            if (word == null || word.length() <= 0) {
                return 0;
            }
            final char[] chars = word.toCharArray();
            Node cur = root;
            for (int i = 0; i < chars.length; i++) {
                char aChar = chars[i];
                int path = aChar - 'a';
                Node node = cur.next[path];
                if (node == null) {
                    return 0;
                }
                if (i == chars.length - 1) {
                    return node.end;
                }
                cur = node;
            }
            return 0;
        }

        public void delete(String word) {
            if (word == null || word.length() <= 0) {
                return;
            }
            if (search(word) == 0) {
                return;
            }
            final char[] chars = word.toCharArray();
            Node cur = root;
            for (int i = 0; i < chars.length; i++) {
                char aChar = chars[i];
                int path = aChar - 'a';
                Node node = cur.next[path];
                // 当前节点的pass为0的话  直接去掉后面的指针指向
                if ((--cur.pass) == 0) {
                    cur.next[path] = null;
                    return;
                }
                // 最后一个尾节点
                if (i == chars.length - 1) {
                    if ((--cur.end) == 0) {
                        cur.next[path] = null;
                        return;
                    }
                }
                cur = node;
            }
        }


        public int prefixNumber(String pre) {
            if (pre == null || pre.length() <= 0) {
                return 0;
            }
            Node cur = root;
            final char[] chars = pre.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int path = chars[i] - 'a';
                final Node node;
                if ((node = cur.next[path]) == null) {
                    return 0;
                }
                if (i == chars.length - 1) {
                    return node.pass;
                }
                cur = node;
            }
            return 0;
        }
    }

}
